We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(1)}$ communication rounds in the \Congest model. Here, $n$ and $D$ denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of $O(n^2)$, and it nearly matches the $\tilde{\Omega}(D+ \sqrt{n})$ round complexity lower bound. The development of the algorithm contains two results of independent interest: (i) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of a spanning tree of average stretch $n^{o(1)}$. (ii) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of an $n^{o(1)}$-congestion approximator consisting of the cuts induced by $O(\log n)$ virtual trees. The distributed representation of the cut approximator allows for evaluation in $(D+\sqrt{n})\cdot n^{o(1)}$ rounds. All our algorithms make use of randomization and succeed with high probability.
展开▼
机译:我们提出了在$(D + \ sqrt {n})\ cdot n ^ {o()中运行的无向加权网络中单商品最大流量的$(1 + o(1))$近似近似分布式算法1)} $通讯在\ Congest模型中进行回合。这里,$ n $和$ D $分别表示节点数和网络直径。这是对$ O(n ^ 2)$的小范围的首次改进,它几乎与$ \ tilde {\ Omega}(D + \ sqrt {n})$复杂度下限匹配。该算法的开发包含两个独立关注的结果:(i)平均伸展$ n ^的生成树的$(D + \ sqrt {n})\ cdot n ^ {o(1)} $轮分布结构。 {o(1)} $。 (ii)一个$(D + \ sqrt {n})\ cdot n ^ {o(1)} $轮分布的$ n ^ {o(1)} $拥塞近似值,它由$引起的削减组成O(\ log n)$虚拟树。割近似器的分布式表示允许在$(D + \ sqrt {n})\ cdot n ^ {o(1)} $轮中进行评估。我们所有的算法都利用随机化,并且成功率很高。
展开▼